package algotithm.acwing.math.test875;

/**
 * @author 25068
 * @Date 2021/5/31 21:16
 * @Title AcWing 875. 快速幂
 */
import java.io.*;
public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        int t = n;
        while (t-- > 0) {
            String[] str = reader.readLine().split(" ");
            long a = Long.parseLong(str[0]);
            long b = Long.parseLong(str[1]);
            long p = Long.parseLong(str[2]);
            long res = 1;
            while (b != 0) {
                if (b % 2 == 1) {
                    res = res * a % p;
                }
                b /= 2;
                a = a * a % p;
            }
            writer.write(res % p + "\n");
        }
        writer.flush();
        writer.close();
        reader.close();

    }


}
